home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2009 February / PCWFEB09.iso / Software / Resources / Chat & Communication / Digsby build 37 / digsby_setup.exe / lib / util / lrucache.pyo (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2008-10-13  |  4.0 KB  |  156 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyo (Python 2.5)
  3.  
  4. from __future__ import with_statement
  5. from collections import deque
  6. from threading import RLock
  7. from functools import wraps
  8. from pprint import pformat
  9.  
  10. def lru_cache(maxsize):
  11.     lck = RLock()
  12.     
  13.     def decorating_function(f):
  14.         cache = { }
  15.         queue = deque()
  16.         refcount = { }
  17.         
  18.         def wrapper(*args, **kwargs):
  19.             lck.__enter__()
  20.             
  21.             try:
  22.                 _cache = cache
  23.                 _len = len
  24.                 _refcount = refcount
  25.                 _maxsize = maxsize
  26.                 queue_append = queue.append
  27.                 queue_popleft = queue.popleft
  28.                 key = args
  29.                 
  30.                 try:
  31.                     result = _cache[key]
  32.                 except KeyError:
  33.                     lck
  34.                     lck
  35.                     result = _cache[key] = f(*args, **kwargs)
  36.                 except:
  37.                     lck
  38.  
  39.                 queue_append(key)
  40.                 _refcount[key] = _refcount.get(key, 0) + 1
  41.                 while _len(_cache) > _maxsize:
  42.                     k = queue_popleft()
  43.                     _refcount[k] -= 1
  44.                     if not _refcount[k]:
  45.                         del _cache[k]
  46.                         del _refcount[k]
  47.                         continue
  48.                     lck
  49.                 if _len(queue) > _maxsize * 4:
  50.                     for i in [
  51.                         None] * _len(queue):
  52.                         k = queue_popleft()
  53.                         if _refcount[k] == 1:
  54.                             queue_append(k)
  55.                             continue
  56.                         _refcount[k] -= 1
  57.                     
  58.             finally:
  59.                 pass
  60.  
  61.             return result
  62.  
  63.         wrapper = (None, None, None, None, None, wraps(f))(wrapper)
  64.         return wrapper
  65.  
  66.     return decorating_function
  67.  
  68.  
  69. class MyDoublyLinkedListNode(object):
  70.     __slots__ = [
  71.         'data',
  72.         'prev',
  73.         'next']
  74.     
  75.     def __init__(self, data, prev = None, next = None):
  76.         self.data = data
  77.         self.prev = prev
  78.         self.next = next
  79.  
  80.     
  81.     def remove(self):
  82.         if self.prev is not None:
  83.             self.prev.next = self.next
  84.         
  85.         self.next.prev = self.prev
  86.  
  87.     
  88.     def append(self, node):
  89.         if self.next is not None:
  90.             raise NotImplmentedError("I don't have use for real insertion")
  91.         
  92.         self.next = node
  93.         node.prev = self
  94.  
  95.     
  96.     def __repr__(self):
  97.         return '%s(%r, %r)' % (self.__class__.__name__, self.data, self.next)
  98.  
  99.  
  100.  
  101. class LRU(dict):
  102.     
  103.     def __init__(self, limit):
  104.         self._limit = limit
  105.         self._ll_head = self._ll_last = MyDoublyLinkedListNode(None)
  106.         self._ll_mapping = { }
  107.         self.lock = RLock()
  108.  
  109.     
  110.     def __setitem__(self, key, value):
  111.         self.lock.__enter__()
  112.         
  113.         try:
  114.             if self._ll_last.data == key:
  115.                 return dict.__setitem__(self, key, value)
  116.             
  117.             if key in self:
  118.                 self._ll_mapping[key].remove()
  119.             elif len(self) == self._limit:
  120.                 self.pop_lru_key()
  121.             
  122.             new_node = MyDoublyLinkedListNode(key)
  123.             self._ll_last.append(new_node)
  124.             self._ll_last = new_node
  125.             self._ll_mapping[key] = new_node
  126.             dict.__setitem__(self, key, value)
  127.         finally:
  128.             pass
  129.  
  130.  
  131.     
  132.     def pop_lru_key(self):
  133.         key = self._ll_head.next.data
  134.         dict.__delitem__(self, key)
  135.         del self._ll_mapping[key]
  136.         self._ll_head.next.remove()
  137.         return key
  138.  
  139.     
  140.     def __delitem__(self, key):
  141.         raise NotImplmentedError('Not necessary for LRU Cache')
  142.  
  143.  
  144. if __name__ == '__main__':
  145.     c = LRU(3)
  146.     print c
  147.     c['a'] = 1
  148.     c['b'] = 2
  149.     c['c'] = 3
  150.     print c
  151.     c['c'] = 5
  152.     print c
  153.     c['a'] = 6
  154.     print c
  155.  
  156.